//
// Created by 麻再挺 on 2021/12/22.
//

#include "straight_sort.h"

//自定义的输出函数
void print(int a[], int n, int i) {
    printf("%d:", i);
    for (int j = 0; j < n; j++) {
        printf("%d", a[j]);
    }
    printf("\n");
}

void Straight_Insert_Sort(int a[], int length) {
    for (int i = 1; i < length; ++i) {
        // 需要移动
        // 若第 i 个元素大于 i-1 元素则直接插入；反之，需要找到适当的插入位置后在插入。
        if (a[i] < a[i - 1]) {
            int j = i - 1;
            int x = a[i];
            // 循环移动
            // /采用顺序查找方式找到插入的位置，在查找的同时，将数组中的元素进行后移操作，给插入元素腾出空间
            while (j > -1 && x < a[j]) {
                a[j + 1] = a[j];
                j--;
            }
            // 插入到正确的位置
            a[j + 1] = x;
        }
        print(a, length, i);//打印每次排序后的结果
    }
}

void B_Straight_Insert_Sort(int a[], int length) {
    // 最小索引, 最大索引, 中位
    int low = 0, high = 0, mid = 0;
    // 临时变量值
    int tmp = 0;
    // 遍历排序
    for (int i = 1; i < length; ++i) {
        // 计算各变量的值
        low = 0;
        high = i - 1;
        tmp = a[i];
        // 采用折半查找法判断插入位置，最终变量 low 表示插入位置
        while (low <= high) {
            // 计算中位索引
            mid = (high + low) / 2;
            // 计算索引
            if (a[mid] > tmp) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        // 有序表中插入位置后的元素统一后移
        for (int j = i; j > low; j--) {
            a[j] = a[j - 1];
        }
        // 插入元素
        a[low] = tmp;
        print(a, length, i);//打印每次排序后的结果
    }
}

void Two_Straight_Insert_Sort(int a[], int tmp[], int length) {
    // 分别记录temp数组中最大值和最小值的位置
    int first = 0, final = 0, k = 0;
    tmp[0] = a[0];
    // 遍历
    for (int i = 1; i < length; ++i) {
        // 待插入元素比最小的元素小
        if (a[i] < tmp[first]) {
            // 计算最小的位置
            first = (first - 1 + length) % length;
            tmp[first] = a[i];
        } else if (a[i] > tmp[final]) {
            // 待插入元素比最大元素大
            final = (final + 1 + length) % length;
            tmp[final] = a[i];
        } else {
            // 插入元素比最小大，比最大小
            k = (final + 1 + length) % length;
            // 当插入值比当前值小时，需要移动当前值的位置
            while (tmp[((k - 1) + length) % length] > a[i]) {
                tmp[(k + length) % length] = tmp[(k - 1 + length) % length];
                k = (k - 1 + length) % length;
            }
            //插入该值
            tmp[(k + length) % length] = a[i];
            //因为最大值的位置改变，所以需要实时更新final的位置
            final = (final + 1 + length) % length;
        }
    }

    // 将排序记录复制到原来的顺序表里
    for (k = 0; k < length; k ++) {
        a[k] = tmp[(first + k) % length];
    }
}





















